package String;

public class _583_DeleteOperationforTwoStrings {
    //hint:longest common subsequence problem,over time limited
    public int minDistance0(String word1, String word2) {
        return word1.length()+word2.length() - lcs(word1, word2, word1.length()-1, word2.length()-1);
    }

    public int lcs(String word1, String word2, int pos1, int pos2) {
        if (pos1 < 0 || pos2 < 0) {
            return 0;
        }
        if (word1.charAt(pos1) == word2.charAt(pos2)) {
            return 1 + lcs(word1, word2, pos1 - 1, pos2 - 1);
        } else {
            return Math.max(lcs(word1, word2, pos1 - 1, pos2),lcs(word1,word2,pos1,pos2-1));
        }
    }

    /////////////////////////////////////////////////////////
    //hint:use memory to hold the redundant calculation's result
    public int minDistance(String word1, String word2) {
        int[][] memo = new int[word1.length()][word2.length()];
        return word1.length()+word2.length()-2*lcsM(word1, word2, word1.length() - 1, word2.length() - 1, memo);
    }

    public int lcsM(String word1, String word2, int pos1, int pos2, int[][] memo) {
        if (pos1 < 0 || pos2 < 0) {
            return 0;
        }
        if (memo[pos1][pos2] > 0) {
            return memo[pos1][pos2];
        }
        if (word1.charAt(pos1) == word2.charAt(pos2)) {
            memo[pos1][pos2] = 1 + lcsM(word1, word2, pos1 - 1, pos2 - 1, memo);
        } else {
            memo[pos1][pos2] =  Math.max(lcsM(word1, word2, pos1-1, pos2, memo), lcsM(word1, word2, pos1, pos2 - 1, memo));
        }
        return memo[pos1][pos2];
    }

}
